1. Field of the Invention
The present invention relates in general to data compression systems and in particular to a data compression system and method for dynamically encoding data into a compressed format and decoding the compressed format without the use of stored or referenced symbol tables or encoding trees for increased efficiency for some data sets.
2. Related Art
Data comprised of text, sounds, images, and video can be encoded so that fewer bits are used to store, transmit, or process the data more efficiently. After the encoded data is stored, transmitted, or processed, the encoded data is decoded to obtain the original data. Encoded data can save storage space of a particular storage medium or can reduce the time it takes to transmit data from one location to another. Thus, current data encoding systems and methods are very important, useful and popular.
As a result, many different data encoding systems and methods exist. This is because the efficiency of any data compression scheme is dependent on the data that is being compressed. One basic type of data encoding system that is used as a basis for many data compression systems is Huffman coding. Huffman coding is a data compression technique that varies the length of the encoded symbol in proportion to its information content. In other words, when a symbol or token is used frequently, a relatively short binary string is used to represent the symbol or token in a compressed stream. Huffman codes can be properly decoded because they obey the prefix property, which means that no code can be a prefix of another code, and so the complete set of codes can be represented as a binary tree, known as a Huffman tree. Each leaf of the Huffman tree corresponds to a letter. The goal is to build a tree with the minimum external path weight. Huffman coding requires a stored or referenced encoding a tree symbol for proper decoding.
Run-length encoding is another basic encoding system. Run-length encoding involves replacing strings of repeated characters, or other units of data, with a single character and a count. For example, a recurring sequence of numbers is first identified and then that sequence is represented with a single number. As a result, run-length encoding can only efficiently compress data that is repetitive. For text files, a similar technique is key-word encoding. Key-word encoding involves replacing frequently occurring words with a 2-byte token. This replacement saves one or more bytes of storage for every instance of that word in a text file. Key-word encoding also requires a stored or referenced symbol table for proper decoding.
Another compression system that is frequently used to compress image data is the Lempel-Ziv Welch (LZW) compression system. LZW compression relies on the reoccurrence of byte sequences or strings in its input. A table mapping input strings to their associated output codes is maintained. Mappings for all possible strings of length one are initially contained in the table. Input is taken one byte at a time in order to determine the longest initial string present in the table. The code for the longest initial string is first output, and then the string is extended with one more input byte.
Next, a new entry is added to the table mapping the extended string to the next unused code and can be obtained by incrementing a counter. The process is repeated, starting from the input byte. The number of bits in an output code (the maximum number of entries in the table) is typically fixed, and once this limit is reached, no more entries are added. Decompression can be accomplished by receiving the compressed code signals and generating a string table similar to that constructed during compression to produce a lookup table of received code signals. This enables recovery of the data character signals comprising a stored string. Thus, a stored or referenced symbol table is required for proper decoding.
From the foregoing it will be apparent that there is a need to encode data dynamically and to decode the encoded data without the use of stored or referenced symbol tables or encoding trees for increased efficiency for some data sets. Therefore, what is needed is a system and method to realize adaptive field encoding and decoding of data.
Whatever the merits of the above mentioned systems and methods, they do not achieve the benefits of the present invention.